package Test;

/**
 * @author Kevin
 * @date 2020/3/1 11:40
 */
public class HeapSort {
    public static void sort(int[] arr) {
        if (arr.length <= 1) return;

        buildHeap(arr);

        int k = arr.length - 1;
        while (k > 0) {
            swap(arr, 0, k);//将堆顶—最大元素和k交换
            heapify(arr, --k, 0);//重新使得堆顶成最大元素
        }
    }

    public static void buildHeap(int[] arr) {
        for (int i = (arr.length-1)/2; i >= 0; i--) {
            heapify(arr, arr.length-1, i);
        }
    }
    //自上而下堆化
    public static void heapify(int[] a, int k, int i) {
        while (true) {
            int maxPos = i;
            if (i * 2 + 1 <= k && a[i * 2 + 1] > a[i]) {
                maxPos = i * 2 + 1;
            }
            if (i * 2 + 2 <= k && a[i * 2 + 2] > a[maxPos]) {
                maxPos = 2 * 2 + 2;
            }
            if (maxPos == i) {
                break;
            }
            swap(a, i, maxPos);
            i = maxPos;
        }
    }


    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }



}
